namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0035. 搜索插入位置")]
    public class No0035_SearchInsert : AbsBaseTestItem
    {
        /*
        给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

        你可以假设数组中无重复元素。
        */

        public override void OnTest()
        {
            Assert.TestExe(SearchInsert, new int[] { 1, 3, 5, 6 }, 5, 2);
            Assert.TestExe(SearchInsert, new int[] { 1, 3, 5, 6 }, 2, 1);
            Assert.TestExe(SearchInsert, new int[] { 1, 3, 5, 6 }, 7, 4);
            Assert.TestExe(SearchInsert, new int[] { 1, 3, 5, 6 }, 0, 0);

            Assert.TestExe(SearchInsert2, new int[] { 1, 3, 5, 6 }, 5, 2);
            Assert.TestExe(SearchInsert2, new int[] { 1, 3, 5, 6 }, 2, 1);
            Assert.TestExe(SearchInsert2, new int[] { 1, 3, 5, 6 }, 7, 4);
            Assert.TestExe(SearchInsert2, new int[] { 1, 3, 5, 6 }, 0, 0);
        }

        /// <summary>
        /// 自己的方法
        /// </summary>
        public int SearchInsert(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0)
            {
                return 0;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] >= target)
                {
                    return i;
                }
            }
            return nums.Length;
        }

        /// <summary>
        /// 官方 二分法
        /// </summary>
        public int SearchInsert2(int[] nums, int target)
        {
            int n = nums.Length;
            int left = 0, right = n - 1, ans = n;
            while (left <= right)
            {
                int mid = ((right - left) >> 1) + left;
                if (target <= nums[mid])
                {
                    ans = mid;
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return ans;
        }
    }
}
